package LeetCode.month01.day10;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

public class No20 {
    public static void main(String[] args) {
        System.out.println(isValid("()"));
    }
    public static boolean isValid(String s) {
        Deque<Character> deque = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(c=='('||c=='['||c=='{') deque.add(s.charAt(i));
            else{
                if(deque.size()==0) return false;
                if(c==')'){
                    if(deque.getLast()!='(') return false;
                }
                if(c==']'){
                    if(deque.getLast()!='[') return false;
                }
                if(c=='}'){
                    if(deque.getLast()!='{') return false;
                }
                deque.removeLast();
            }
        }
        if(deque.size()!=0) {
            return false;
        }
        return true;
    }
}
